type MIN_STACK_ITEM = {
    val: number,
    idx: number,
};

function sumSubarrayMins(arr: number[]): number {
    // 1 2 3 4
    // 1*2^3 + 2 *2^2 + 3 * 2^1 + 4 * 2^0
    // 8+8+

    // 3 0,0
    // 1 1,2
    // 2 0,1
    // 4 0,0
    // 1+2^1*2^2+1*2^1+1
    // 1+8+2+1=12
    // 3+8+4+4=17

    // const int MOD = 1e9+7;
    // const int arr_len = arr.length;
    // vector<int> dp(arr_len);
    const MOD = 1e9+7;
    // TODO: use MOD!!!
    const arr_len = arr.length;
    const dp = new Array(arr_len);
    // const min_stack = [{val: 0, idx: -1}];
    dp[0] = arr[0];
    const min_stack = [{val: arr[0], idx: 0}];
    for (let i = 1; i < arr_len; i++)
    {
        while (min_stack.length > 0 && arr[i] <= min_stack[min_stack.length-1].val)
        {
            min_stack.pop();
        }
        const last_min_idx =  (min_stack.length > 0) ? min_stack[min_stack.length-1].idx : -1;
        const seg_min_sum = (i - last_min_idx) * arr[i];
        const old_dp_val = (last_min_idx == -1) ? 0 : dp[last_min_idx];
        dp[i] = old_dp_val + seg_min_sum;
        min_stack.push({val: arr[i], idx: i});
    }

    let ret_min_sum = 0;
    for (let i = 0; i < arr_len; i++)
    {
        ret_min_sum += dp[i];
    }
    return ret_min_sum;
};

const inputs = [
    [3,1,2,4],
    [11,81,94,43,3],
];
inputs.forEach((input_arr) => {
    console.log(input_arr, sumSubarrayMins(input_arr));
});